package CareerUp.ShortestPathInMattrix;

import java.util.ArrayList;

/**
 * Use bellman-ford method to find the shortest path in a graph
 * 
 * @author Xi
 * 
 */
public class Map {

	public static void main(String[] argv) {
		Node nodeA = new Node("A");
		Node nodeB = new Node("B");
		Node nodeC = new Node("C");
		Node nodeD = new Node("D");
		Node nodeE = new Node("D");

		ArrayList<Node> nodes1 = new ArrayList<Node>();
		nodes1.add(nodeB);
		nodes1.add(nodeC);
		nodeA.setConnectNodes(nodes1);

		ArrayList<Node> nodes2 = new ArrayList<Node>();
		nodes2.add(nodeA);
		nodes2.add(nodeD);
		nodeB.setConnectNodes(nodes2);

		ArrayList<Node> nodes3 = new ArrayList<Node>();
		nodes3.add(nodeA);
		nodes3.add(nodeD);
		nodeC.setConnectNodes(nodes3);

		ArrayList<Node> nodes4 = new ArrayList<Node>();
		nodes4.add(nodeB);
		nodes4.add(nodeC);
		nodes4.add(nodeE);
		nodeD.setConnectNodes(nodes4);

		ArrayList<Node> nodes5 = new ArrayList<Node>();
		nodes5.add(nodeD);
		nodeE.setConnectNodes(nodes5);

		ArrayList<Node> nodes = new ArrayList<Node>();
		nodes.add(nodeA);
		nodes.add(nodeB);
		nodes.add(nodeC);
		nodes.add(nodeD);
		nodes.add(nodeE);

		Map m = new Map(nodes);
		m.setStartNode(m.nodes.get(0));

		ArrayList<Node> startNode = new ArrayList<Node>();
		startNode.add(m.nodes.get(0));
		m.getShortestPath(startNode);

		m.showResult();

	}

	ArrayList<Node> nodes = new ArrayList<Node>(); // map is composite by all
													// the nodes

	Map(ArrayList<Node> n) {
		nodes = n;
	}

	public void setStartNode(Node n) {
		n.isSource = true;
		n.distance = 0;
	}

	/**
	 * 
	 * Start from node[0], recursively find the reachable nodes and update the
	 * shortest distance (bellman-ford method)
	 */
	public void getShortestPath(ArrayList<Node> currentLevel) {
		for (int i = 0; i < currentLevel.size(); i++) {
			Node currentNode = currentLevel.get(i);
			// since it has been reached, set the flag of will-be-reach to
			// false
			currentNode.willBeReach = false;
			currentNode.isReached = true;

			// relaxation- update the distance
			for (int j = 0; j < currentNode.connectedNodes.size(); j++) {
				Node currentReachedNode = currentNode.connectedNodes.get(j);

				if (currentNode.distance + 1 < currentReachedNode.distance)
					currentReachedNode.distance = currentNode.distance + 1;

				// if the reached node never act as source, add it to next
				// level, if no such node exists, we reach the end
				if (currentReachedNode.isReached == false)
					currentReachedNode.willBeReach = true;

			}
		}

		// collect the next level nodes if there exists any
		ArrayList<Node> nextLevel = new ArrayList<Node>();
		for (int i = 0; i < nodes.size(); i++) {
			if (nodes.get(i).willBeReach == true)
				nextLevel.add(nodes.get(i));
		}

		// judge whether we reach the end
		if (nextLevel.size() != 0)
			getShortestPath(nextLevel);

	}

	public void showResult() {
		for (int i = 0; i < nodes.size(); i++) {
			if (nodes.get(i).isSource == true)
				System.out.println("Start from: " + nodes.get(i).name);
			else
				System.out.println(nodes.get(i).name + " : " + nodes.get(i).distance);
		}
	}
}
